package gold.gold03;

/**
 *
 */
public class S0801三步问题 {




    /**
     * 15, 粗暴的动态规划。
     * 因为一共只用到数组的最后几个值, 所以可以考虑用4个变量替代
     */
    public int waysToStep(int n) {
        if(n < 4) return n==3? 4 : (n == 2? 2: 1);
        int[] stepCount = new int[n];
        stepCount[0] = 1;
        stepCount[1] = 2;
        stepCount[2] = 4;
        for(int i = 3; i < n; i++){
            stepCount[i] = ((stepCount[i - 1] + stepCount[i - 2])%1000000007 + stepCount[i - 3])%1000000007;
        }
        return stepCount[n - 1];
    }
    // 15, 就这样, 少一点数组的开销, 速度上没变化。
    public int waysToStep2(int n) {
        if(n < 4) return n==3? 4 : (n == 2? 2: 1);
        int[] stepCount = new int[4];
        stepCount[0] = 1;
        stepCount[1] = 2;
        stepCount[2] = 4;
        for(int i = 3; i < n; i++){
            stepCount[i%4] = ((stepCount[(i - 1)% 4] + stepCount[(i - 2) % 4])%1000000007 + stepCount[(i - 3) % 4])%1000000007;
        }
        return stepCount[(n - 1) % 4];
    }

    /**
     * 91, 不能理解为什么使用abcd要比使用数组快, 数组索引应该也是O(1)复杂度
     * 可能和jvm对堆和常量池的处理有关系。
     */
    public int waysToStep3(int n) {
        if(n < 4) return n==3? 4 : (n == 2? 2: 1);
        int a = 1, b = 1, c = 2, d = 4;
        for (int i = 3; i <= n; i++) {
            d = ((a + b) % 1000000007 + c) % 1000000007;
            a = b;
            b = c;
            c = d;
        }
        return d;
    }

    /**
     * 0ms, 上面的20ms, 矩阵快速幂, 神奇。
     * https://leetcode-cn.com/problems/three-steps-problem-lcci/solution/mei-ri-suan-fa-day-80-suo-you-ren-du-hui-zuo-de-ru/
     */
    static final int mod = 1000000007;
    public static int waysToStep4(int n) {
        int ans = 0;
        if (n < 3)
            return n;
        if (n == 3)
            return 4;

        long[] f = new long[]{1, 2, 4};

        long[][] A = new long[][]{
                {1, 1, 1},
                {1, 0, 0},
                {0, 1, 0}
        };
        long[][] B = matPow(A, n -3);
        for (int i = 0; i < 3; i++) {
            ans += ((B[0][i]* f[2 - i]) % mod) ;
            ans %= mod;
        }
        return ans;
    }

    //二分法 矩阵快速幂
    private static long[][] matPow(long[][] mat, int k){
        long[][] tmp;
        if (k == 1){
            tmp = new long[3][3];
            for (int i = 0; i < 3; i++) {
                for (int j = 0; j < 3; j++) {
                    tmp[i][j] = mat[i][j];
                }
            }
            return tmp;
        }
        tmp= matPow(mat, k >> 1);
        tmp = matMul(tmp, tmp);
        return ((k & 1) == 0) ? tmp : matMul(tmp, mat);
    }
    /**
     * 矩阵相乘
     */
    private static long[][] matMul(long[][] A, long[][] B){
        long[][] t = new long[3][3];

        for (int i = 0; i < 3; i++) {
            for (int j = 0; j < 3; j++) {

                for (int p = 0; p < 3; p++)
                    t[i][j] += (A[i][p] * B[p][j])% mod;

            }
        }
        return t;
    }
}
